package labuladong.第四章;

public class findLostNum {
    public static void main(String[] args) {
        int[] arr = {2, 4, 3, 1, 7, 5};
//        System.out.println(missingNumber(arr));
        System.out.println(missingNumber2(arr));
        System.out.println(missingNumber3(arr));
    }

    public static int missingNumber(int[] nums) {
        int n = nums.length;
        int res = 0;
        // 先和补位异或
        res ^= n;
        // 再和其他元素异或
        for (int i=0; i<n; i++) {
            res ^= i ^= nums[i];
        }
        return res;
    }

    public static int missingNumber2(int[] nums) {
        int n = nums.length;
        // 计算和
        int expect = (1+n)*(2+n)/2;
        int sum = 0;
        for(int i=0; i<n; i++) {
            sum += nums[i];
        }
        return expect - sum;
    }

    public static int missingNumber3(int[] nums) {
        int n = nums.length;
        int num = 0;
        for(int i=1; i<=n; i++) {
            num = num + i - nums[i-1];
        }
        return num + n + 1;
    }
}
